package com.lmz.project.redis.interview;

import java.util.Arrays;

/**
 * 计算两个正序数组的中位数
 */
public class CalculateMedian {
    public static void main(String[] args) {
        //[2,2,4,4]
        //[2,2,2,4,4]
        int[] num1 = {2,2,4,4};
        int[] num2 ={2,2,2,4,4};
        int[] medianSortedArrays = findMedianSortedArrays(num1, num2);
        System.out.println(Arrays.toString(medianSortedArrays));
        if(medianSortedArrays.length % 2 ==0){
            int a = medianSortedArrays[medianSortedArrays.length/2];
            int b = medianSortedArrays[medianSortedArrays.length/2-1];
            System.out.println((a+b) /2.0);
        }else {
            System.out.println(medianSortedArrays[medianSortedArrays.length/2]/1.0);
        }
    }

    public static int[] findMedianSortedArrays(int[] nums1, int[] nums2) {
        int left =0;
        int right = nums1.length + nums2.length-1;
        int[] mergeArr = new int[nums1.length+nums2.length];
        int i =0;
        for (int j = 0; j < nums1.length; j++) {
            mergeArr[i] = nums1[j];
            i++;
        }
        for (int j = 0; j < nums2.length; j++) {
            mergeArr[i] = nums2[j];
            i++;
        }
        int[] temp = new int[nums1.length+nums2.length];
        separateArr(mergeArr,left,right,temp);
        return mergeArr;
    }

    public static void separateArr(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            separateArr(arr, 0, mid, temp); //分离左侧部分
            separateArr(arr, mid + 1, right, temp); //分离右侧部分
            //合并
            mergeSort(arr,left,mid,right,temp);
        }
    }


    public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                i++;
            } else {
                temp[t] = arr[j];
                j++;
            }
            t++;
        }
        //将左侧剩余部分添加到临时数组
        while (i<=mid){
            temp[t] = arr[i];
            i++;
            t++;
        }
        //将右侧侧剩余部分添加到临时数组
        while (j<=right) {
            temp[t] = arr[j];
            j++;
            t++;
        }
        t=0;
        int leftTemp = left;
        while (leftTemp<=right) {
            arr[leftTemp] = temp[t];
            t++;
            leftTemp++;
        }
    }
}
